package zw_801_900.zw_844_比较含退格的字符串;

class Solution {

    public static void main(String[] args) {
        String s = "ab#c", t = "ad#c";
        boolean b = backspaceCompare(s, t);
        System.out.println(b);
    }

    /**
     * 双指针
     *
     * @param S
     * @param T
     * @return
     */
    public static boolean backspaceCompare(String S, String T) {
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;
        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (S.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (T.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
                if (S.charAt(i) != T.charAt(j)) {
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;
    }


    /**
     * 重构
     *
     * @param S
     * @param T
     * @return
     */
//    public boolean backspaceCompare(String S, String T) {
//        return build(S).equals(build(T));
//    }
//
//    public String build(String str) {
//        StringBuffer ret = new StringBuffer();
//        int length = str.length();
//        for (int i = 0; i < length; ++i) {
//            char ch = str.charAt(i);
//            if (ch != '#') {
//                ret.append(ch);
//            } else {
//                if (ret.length() > 0) {
//                    ret.deleteCharAt(ret.length() - 1);
//                }
//            }
//        }
//        return ret.toString();
//    }
}
